213E - Two Permutations - CodeForces Solution

#include<bits/stdc++.h>
#include<cmath>
#define ll unsigned long long
#define For(i,a,b) for(ll i=a;i<=b;i++)
#define Rof(i,a,b) for(ll i=a;i>=b;i--)
#define N 200010
#define pb push_back
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define SP fixed<<setprecision(12)
#define mk make_pair
#define pque priority_queue

using namespace std;
int a[N],b[N],pos[N],ans=0;
ll has[N<<2],sz[N<<2];
ll mi[N],ha,sum;
int n,m;

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void pushup(int x){
	sz[x]=sz[ls]+sz[rs];
	has[x]=has[ls]*mi[sz[rs]]+has[rs];
}
void add(int x,int l,int r,int u,int v){
	if(l==r){
		if(!v) sz[x]--;
		else sz[x]++;
		has[x]=v;
		return;
	}
	int mid=(l+r)>>1;
	if(u<=mid) add(lson,u,v);
	else add(rson,u,v);
	pushup(x);
}

int main()
{
    mi[0]=1;
    n=read(),m=read();
    For(i,1,n){
    	a[i]=read();
    	ha=ha*233+a[i];
    	mi[i]=mi[i-1]*233;
    	sum+=mi[i-1];
	}
	For(i,1,m) b[i]=read(),pos[b[i]]=i;
	For(i,1,m){
		if(i>n) add(1,1,m,pos[i-n],0);
		add(1,1,m,pos[i],i);
		int d=i-n;
		if(d>=0 && has[1]==d*sum+ha) ans++;
	}
	cout<<ans;
    return 0;
}